/*
 * @Author: szx
 * @Date: 2021-10-31 13:09:58
 * @LastEditTime: 2021-10-31 14:20:27
 * @Description:
 * @FilePath: \leetcode\500-599\567\567.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
// class Solution {
//    public:
//     bool checkInclusion(string s1, string s2) {
//         if (s1.size() > s2.size()) {
//             return false;
//         }
//         int n = s1.size();
//         vector<int> cnt(26);
//         for (char ch : s1) {
//             cnt[ch - 'a']++;
//         }
//         int diff = n;
//         for (int i = 0; i < n; i++) {
//             diff += cnt[s2[i] - 'a'] > 0 ? -1 : 1;
//             cnt[s2[i] - 'a']--;
//         }
//         if (!diff && isZero(cnt)) {
//             return true;
//         }

//         for (int i = n; i < s2.length(); i++) {
//             diff += cnt[s2[i] - 'a'] > 0 ? -1 : 1;
//             cnt[s2[i] - 'a']--;
//             diff += cnt[s2[i - n] - 'a'] < 0 ? -1 : 1;
//             ++cnt[s2[i - n] - 'a'];
//             if (diff == 0 && isZero(cnt)) {
//                 return true;
//             }
//         }
//         return false;
//     }
//     bool isZero(vector<int> v) {
//         for (int i : v) {
//             if (i != 0) {
//                 return false;
//             }
//         }
//         return true;
//     }
// };

class Solution {
   public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        vector<int> cnt(26);
        for (int i = 0; i < n; ++i) {
            --cnt[s1[i] - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2[right] - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2[left] - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    Solution s;
    cout << s.checkInclusion("abcdxabcde", "abcdeabcdx") << endl;

    return 0;
}